package com.powernode.dataStructure;

public class BinarySearch {

    public static void main(String[] args) {
        int []a = {1,2,3,4,5,6,7,8,9,10};
        int target = -3;
        System.out.println("binarySearchBase(a,target) = " + binarySearchBase(a, target));
    }

    /**
     * 1.定义i起始指针，j为结束指针
     * 2.取中间索引值，定义变量m = a[(i+j)/2]
     * 3.if m < target , i = m的索引+1
     * (目标值比中间值大，那么比中间值还要小的数据就可以去掉，下一步要往中间值的右区间去找)
     *   if m > target , j = m的索引-1
     * (目标值比中间值小，那么比中间值还要大的数据就可以去掉，下一步要往中间值的左区间去找)
     * 4.比较 i或j 和target对应的值
     *   相等即返回，当i > j返回 -1表示没找到
     * 5.重复第2步
     * @param a 升序数组
     * @param target 查找的值
     * @return 查找的值的索引，-1表示没找到
     */
    public static int binarySearchBase(int []a,int target){
        int i = 0,j=a.length-1;
        while (i<=j){
            //int index_m = (i+j)/2;
            //使用无符号右移，避免出现两个大数相加结果为负数，然后除以2还是负数的问题
            //java中最高位是符号位，两个大数相加最高位可能是1
            int index_m = (i+j)>>>1;
            int m = a[index_m];
            if (m<target){
                i = index_m + 1;
                if (i>a.length-1){
                    //查找的值比数组中最大值还要大
                    return -1;
                }
                if (a[i]==target){
                    return i;
                }
            }else {
                j = index_m - 1;
                if (j<0){
                    //查找的值比数组中最小值还要小
                    return -1;
                }
                if (a[j]==target){
                    return j;
                }
            }
        }
        return -1;
    }

    //更简洁写法
    public static int binarySearchBase2(int []a,int target){
        int i = 0,j=a.length-1; //1.定义i起始指针，j为结束指针
        while (i<=j){
            int index_m = (i+j)>>>1;
            if (target<a[index_m]){
                j = index_m - 1;
            }else if (target>a[index_m]){
                i = index_m + 1;
            }else {
                return index_m;
            }
        }
        return -1;
    }

    /**
     * 当存在重复元素时，取最左边元素
     * @param a 升序数组
     * @param target 查找的值
     * @return 查找的值的索引，-1表示没找到
     */
    public static int binarySearchLeftMost(int []a,int target){
        int i = 0,j=a.length-1; //1.定义i起始指针，j为结束指针
        int candidate = -1;//假设没找到
        while (i<=j){
            int index_m = (i+j)>>>1;
            if (target<a[index_m]){
                j = index_m - 1;
            }else if (target>a[index_m]){
                i = index_m + 1;
            }else {
                candidate = index_m;
                j = index_m - 1;//找到后往左缩小边界
            }
        }
        return candidate;
    }

    /**
     * 当存在重复元素时，取最右边元素
     * @param a 升序数组
     * @param target 查找的值
     * @return 查找的值的索引，-1表示没找到
     */
    public static int binarySearchRightMost(int []a,int target){
        int i = 0,j=a.length-1; //1.定义i起始指针，j为结束指针
        int candidate = -1;
        while (i<=j){
            int index_m = (i+j)>>>1;
            if (target<a[index_m]){
                j = index_m - 1;
            }else if (target>a[index_m]){
                i = index_m + 1;
            }else {
                candidate = index_m;
                i = index_m + 1;
            }
        }
        return candidate;
    }

    /**
     * 返回插入点
     * @param a 升序数组
     * @param target 查找的值
     * @return 升序数组a中查找的值target的插入点位置
     */
    public static int binarySearchReturnInsertPoint(int []a,int target){
        int low = 0;
        int high = a.length - 1;

        while (low <= high) {
            int mid = (low + high) >>> 1;
            int midVal = a[mid];

            if (midVal < target)
                low = mid + 1;
            else if (midVal > target)
                high = mid - 1;
            else
                return mid; // key found
        }
        return low ;  // key not found.

    }

}
